/*
    created: 2023/5/2 
    filename: Mysort.c
    author：李东霖
    purpose：排序算法  
*/

#include"Mysort.h"
#include<math.h>
#include<windows.h>

void Swap(int *i, int *j)
{
    int temp = *i;
    *i = *j;
    *j = temp;
}


//冒泡排序
void Bubb_sort(ElemType *arr,int len)
{
    if(arr == NULL || len <= 1) return;
    ElemType *array = arr;
    //定义一个提前出来的标志
    int flag = 1;
    for(int i = 0; i != len - 1; ++i)
    {
        for(int pos = 0; pos != len - i - 1; ++pos)
        {
            if(array[pos]>array[pos+1])
            {   
                flag = 0;
                array[pos] += array[pos+1];
                array[pos+1] = array[pos] - array[pos+1];
                array[pos] -= array[pos+1];
            }
        }
        if(0 == flag) flag = 1;
        else break;
    }
}


//选择排序  
void Select_sort(ElemType *arr,int len)
{
    if(arr == NULL || len <= 1) return;
    ElemType *array = arr;
    //记录最小位置  
    int minpos = 0;
    for(int i = 0; i != len - 1; ++i)
    {
        minpos = i;
        for(int pos = i + 1; pos != len; ++pos)
        {
            if(array[minpos] > array[pos])
            {
                minpos = pos;
            }
        }
        //满足就交换
        if(i != minpos)
        {
            array[i] += array[minpos];
            array[minpos] = array[i] - array[minpos];
            array[i] -= array[minpos];
        }
    }
}

//插入排序  
void Insert_sort(ElemType *arr,int len)
{
    if(arr == NULL || len <= 1) return;
    ElemType *array = arr;
    for(int index = 1; index != len; ++index)
    {
        ElemType elem = array[index];
        int pos = index-1;
        //在有序区查找合适位置
        while( pos >= 0)
        {
            if(array[pos] > elem)
            {
                array[pos+1] = array[pos];
                 --pos;
            }
            else break;
        }
        //优化 减少不必要赋值
        if(index != pos + 1)
        {
            array[pos+1] = elem;
        }
    }
}


//希尔排序  
void Shell_sort(ElemType *arr,int len)
{
    if(arr == NULL || len <= 1) return;
    ElemType *array = arr;
    //定义步长  
    int d = len / 2;
    while(d >= 1)
    {
        for(int i = d; i < len; ++i)
        {
            ElemType elem = array[i];
            int j = i - d;
            while(j >= 0)
            {
                if(array[j] > elem)
                {
                    array[j+d] = array[j];
                    j = j - d;
                }
                else break;
            }
            if(i != j + d)  array[j+d] = elem;
        }
        d = d / 2;
    }
}


//快速排序递归函数  区间为前闭后闭
void RQuick_sort(ElemType *arr,int start, int end)
{
    if(start >= end) return;
    //保存基准元素  
    ElemType elem = arr[start];
    //保存空位
    int s = start;
    int e = end;
    while(s < e)
    {
        //右边
        while(s < e && arr[e] >= elem) --e;
        //左边 
        while(s < e && arr[s] <= elem) ++s;
        //交换
        if(s < e) Swap(&arr[s],&arr[e]);
    }

    //将基准和中间值交换
    Swap(&arr[start],&arr[s]);
    //递归左边  
    RQuick_sort(arr,start,e-1);
    //递归右边  
    RQuick_sort(arr,s+1,end);
}
//快速排序  
void Quick_sort(ElemType *arr,int len)
{
    if( len <= 1) return;
    int start = 0;
    int end = len -1;
    RQuick_sort(arr,start,end);
}

//归并排序的递归函数  
void Merge(ElemType *arr,ElemType *temp,int start, int end)
{
    if(start >=  end) return;
    int mid = start + (end - start)/2;
    //定义区间  [start,mid],[mid+1,end]
    int start1 = start , end1 = mid;
    int start2 = mid+1 , end2 = end;
    Merge(arr,temp,start1,end1);
    Merge(arr,temp,start2,end2);

    //归并  
    int i = start;
    while(start1 <= end1 && start2 <= end2)
    {
        temp[i++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];  
    }
    while(start1 <= end1) temp[i++] = arr[start1++];
    while(start2 <= end2) temp[i++] = arr[start2++];
    //查看它排序情况就打开它
    //for(int i = 0; i != len; ++i) printf("%d ",temp[i]);  printf("\n");
    memmove(arr+start,temp+start,(end-start+1)*sizeof(ElemType));
}

//归并排序 递归 
void RMerge_sort(ElemType *arr,int len)
{
    if(len <= 2) return;
    ElemType* array = arr;
    ElemType temp[len];
    int start = 0;
    int end = len - 1;
    Merge(array,temp,start,end);
}

//归并排序  迭代
void Merge_sort(ElemType *arr,int len)
{
    if(len <= 2) return;
    ElemType* array = arr;
    //定义一个保存有序数组的容器
    ElemType* head = (ElemType*)malloc(sizeof(ElemType)*len);
    //定义区间分段  
    int step;
    //定义区间起始位置  
    int istart;
    //步长
    for(step = 1; step < len; step *= 2)
    {   
        //定义偏移量
        int offset = step * 2;
        for(istart = 0; istart < len; istart += offset)
        {
            //将区间分成两个部分 [low,mid),[mid,max)  
            int low = istart;
            int mid = min(istart+step,len);
            int max = min(istart+offset,len);
    
            //为两个有序数组定义区间  
            int i = low;
            int start1 = low , end1 = mid;
            int start2 = mid , end2 = max;
            //归并  
            while(start1 < end1 && start2 < end2)
            {
                head[i++] = array[start1] < array[start2] ? array[start1++] : array[start2++];  
            }
            while(start1 < end1) head[i++] = array[start1++];
            while(start2 < end2) head[i++] = array[start2++];
        }

        //查看它排序情况就打开它
        // for(int i = 0; i != len; ++i) printf("%d ",head[i]);  printf("\n");
        
        //交换head 和 array数组  head的是排序过一次的，我们要使用head来排序
        //进行下一趟排序  
        ElemType* temp = array;
        array = head;
        head = temp;
    }
    //我们不知道他需要匹配多少次，如果有序的不是array数组则拷贝一下  
    if(array != arr)
    {
        memmove(arr,array,len*sizeof(ElemType));
        head = array;
    }  
    free(head);
}


//初始化堆函数  迭代  传入区间[start,end]
void heapify(ElemType *arr,int start,int end)
{
    //对这个树的每一个非叶子结点都要能够成为一个堆  
    int parent = start;
    int child = 2*start+1;

    while(child <= end)
    {
        //比较出最大的孩子结点  
        if(child + 1 <= end && arr[child] <= arr[child + 1]) ++child;

        //满足条件就退出
        if(arr[child] < arr[parent]) break;
        //完成交换需要重新判断子树的结构是否满足  
        Swap(&arr[child],&arr[parent]);
        parent = child;
        child = 2*parent + 1;
    }
    //查看排序
    // for (int ii=0;ii <= end;ii++) printf("%2d ",arr[ii]);printf("\n");
}

//初始化堆函数  递归  传入区间[start,end]
void Rheapify(ElemType *arr,int start,int end)
{
   
    //对这个树的每一个非叶子结点都要能够成为一个堆  
    int parent = start;
    int child = 2*start+1;
    if(child > end) return;    

    //比较出最大的孩子结点  
    if(child + 1 <= end && arr[child] <= arr[child + 1]) ++child;
    //满足条件就退出
    if(arr[child] < arr[parent]) return;

    //完成交换需要重新判断子树的结构是否满足  
    Swap(&arr[child],&arr[parent]);
    Rheapify(arr,child,end);
    //查看排序
    for (int ii=0;ii <= end;ii++) printf("%2d ",arr[ii]);printf("\n");
}


//堆排序  
void Heap_sort(ElemType *arr,int len)
{
    for(int i = (len-1)/2; i >= 0; --i) Rheapify(arr,i,len-1);
    for(int i = len-1; i > 0; --i)
    {
        Swap(&arr[0],&arr[i]);
        Rheapify(arr,0,i-1);
    }
}

//计数排序  
void Count_sort(ElemType *arr,int len)
{
    if(len <= 1) return;  
    //找到数组的最大值
    int MAX = arr[0];
    for(int i = 1; i != len; ++i)
        if(MAX < arr[i])
            MAX = arr[i];

    //构建一个数组空间  
    ElemType temparr[MAX+1];
    memset(temparr,0,sizeof(temparr));
    for(int i = 1; i != len; ++i)
        ++temparr[arr[i]];

    //查看这个临时数组
    // for (int ii=0;ii<MAX+1;ii++) printf("%2d ",temparr[ii]);printf("\n");

    //组合排序  
    int pos = 0;
    for(int i = 1; i != MAX+1; ++i)
    {
        for(int j = temparr[i]; j != 0; --j)
        {
            arr[pos++] = i;
        }
    }
}


//桶排序 ---实际内存排序采用快排
void Bucket_sort(ElemType *arr,int len)
{
    if(len <= 2) return;

    //首先我们需要准备桶,这里我们就准备5个，因为我的测试函数只有这么大 [0,50]
    int bucket[5][10];  
    int bucketsize[5]; //每个桶的计数器  

    memset(bucket,0,sizeof(bucket));
    memset(bucketsize,0,sizeof(bucketsize));

    //开始将数组分类  
    for(int i = 0; i != len; ++i)
    {
        //分区间，前开后闭  例如：[0,10) 
        bucket[arr[i]/10][bucketsize[arr[i]/10]++] = arr[i];
        // printf("%d ",bucket[arr[i]/10][bucketsize[arr[i]/10]-1]);
        // printf("存放在bucketsize[%d]的第%d个元素中",arr[i]/10,bucketsize[arr[i]/10]);
        // Sleep(1000);
        // printf("\n");
    }
    for(int i = 0; i != 5; ++i)
    {
        //我们看一下桶中的结果
        // for (int ii=0;ii<bucketsize[i];ii++) printf("%d ",bucket[i][ii]);printf("\n");
        //对每个桶进行排序----这里采用快排    
        Quick_sort(bucket[i],bucketsize[i]);
        //我们看一下桶中的结果
        // for (int ii=0;ii<bucketsize[i];ii++) printf("%d ",bucket[i][ii]);printf("\n");
        // printf("***********************************\n");
    }


    // 然后将桶中元素填充到数组arr中  
    for(int i = 0,pos = 0; i != 5; ++i)
    {
        for(int j = 0; j != bucketsize[i]; ++j)
        {
            arr[pos++] = bucket[i][j];
        }
    }
}

//基数排序的排序函数  
void _Radix_sort(ElemType *arr,int len, int exp)
{
    ElemType result[len];
    int bucket[10];    
    memset(bucket,0,sizeof(bucket));
    
    for(int i = 0; i != len; ++i)
    {
        bucket[(arr[i]/exp)%10]++;
    }

    // for (int ii=0;ii<10;ii++) printf("%d ",bucket[ii]);printf("\n");
    // Sleep(1000);

    //调整元素  确定已排序数组下标  
    for(int i = 1; i != 10; ++i)
    {
        bucket[i]+=bucket[i-1];
    }
    // for (int ii=0;ii<10;ii++) printf("%d ",bucket[ii]);printf("\n");
    // Sleep(1000);
    
    //为了保证稳定性，从后往前。因为后面的元素会放在桶的上面
    for(int i = len - 1; i >= 0; --i)
    {
        int iexp = (arr[i]/exp)%10;
        //使用这个下标
        result[bucket[iexp]-1] = arr[i];
        bucket[iexp]--;
    }

    // for (int ii=0;ii<len;ii++) printf("%d ",result[ii]);printf("\n");
    // Sleep(1000);
    memcpy(arr,result,sizeof(ElemType)*len);
    // for (int ii=0;ii<len;ii++) printf("%d ",arr[ii]);printf("\n");
    // Sleep(1000);
}

//基数排序  
void Radix_sort(ElemType *arr,int len)
{   
    if(len <= 1) return;
    ElemType MAX = arr[0];
    //找到最大值，确定最高位数  
    for(int i = 1; i != len; ++i)
    {
        if(MAX < arr[i]) MAX = arr[i];
    }

    for(int exp = 1; MAX/exp != 0; exp*=10)
    {
        //进行排序  
        _Radix_sort(arr,len,exp);
        //查看以下排序结果
        // for (int ii=0;ii<len;ii++) printf("%d ",arr[ii]);printf("\n");
    }
}